package leetcode_1_200;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LeeCode_139_2 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("leet");
        list.add("code");
        System.out.println(wordBreak("leetcode", list));
        List<String> list2 = new ArrayList<>();
        list2.add("apple");
        list2.add("pen");
        System.out.println(wordBreak("applepenapple", list2));
        List<String> list3 = new ArrayList<>();
        list3.add("cats");
        list3.add("dog");
        list3.add("sand");
        list3.add("and");
        list3.add("cat");
        System.out.println(wordBreak("catsandog", list3));
        List<String> list4 = new ArrayList<>();
        list4.add("aa");
        list4.add("aaa");
        list4.add("aaaa");
        list4.add("aaaa");
        list4.add("aaaaa");
        list4.add("b");
        System.out.println(wordBreak("aaaaaaaaaaaaaaaab", list4));
    }
    private static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
}
